package array

/*
LeetCode 0001

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
*/

/*
题解：
在数组nums中找到两个数，这两个数之和须等于一个给定的数target，找到后返回两个数的下标即可。
思路：
该题需要顺序扫描数组，其最优算法的时间复杂度为O(n)。
解法：
顺序扫描数组，对每一个元素n，在map中找target-n，如果找到了，直接返回这两个数的下标；如果找不到，
就将元素n及其下标存入map中（n为key，下标为value），等扫到另一个满足条件的数字，再将其一起取回并返回下标。
*/

// TwoSum 求两数之和
func TwoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		eligibleNum := target - nums[i]
		if _, ok := m[eligibleNum]; ok {
			return []int{m[eligibleNum], i}
		}
		m[nums[i]] = i
	}
	return nil
}
